def test01():
    num_lst = [1, 9, 8, 5, 6, 7, 4, 3, 2]

    l = len(num_lst)

    count_inter = 0
    count_outer = 0
    print(num_lst)
    for i in range(l):
        maxindex = i
        for j in range(i + 1, l):
            count_inter += 1
            if num_lst[maxindex] < num_lst[j]:
                maxindex = j
        if i != maxindex:
            tmp = num_lst[i]
            num_lst[i] = num_lst[maxindex]
            num_lst[maxindex] = tmp
            count_outer += 1
    print(count_inter, count_outer, num_lst)


"""
改进：二元选择排序，即每次分别选出极大值和极小值，然后将极大值放在最左边，极小值放在最右边。
"""


def test02():
    num_lst = [1, 9, 8, 5, 6, 7, 4, 3, 2]
    l = len(num_lst)

    count_inter = 0
    count_outer = 0
    print(num_lst)

    for i in range(l // 2):
        maxindex = i
        minindex = -i - 1
        minorigin = minindex

        for j in range(i + 1, l - i):  # 每次左右都要少比较一个
            count_inter += 1
            if num_lst[maxindex] < num_lst[j]:
                maxindex = j
            if num_lst[minindex] > num_lst[-j - 1]:
                minindex = -j - 1

        if i != maxindex:
            tmp = num_lst[i]
            num_lst[i] = num_lst[maxindex]
            num_lst[maxindex] = tmp
            count_outer += 1
            # 如果最小值被交换过，则更新索引。
            # 由于i是正数，minindex必须是正数（这里是使用的负索引）。
            # 所以，第一个是极小值使用正索引的场景，第二个是极小值使用负索引的场景。
            if i == minindex or i == l + minindex:
                minindex = maxindex

        if minorigin != minindex:
            tmp = num_lst[minorigin]
            num_lst[minorigin] = num_lst[minindex]
            num_lst[minindex] = tmp
            count_outer += 1

    print(num_lst, count_inter, count_outer)

"""
如果一轮比较之后，极大值和极小值相等，那么剩下的所有元素全部相等。
"""

def test03():
    num_lst = [1, 1, 1, 1, 1, 1, 1, 1, 1]
    l = len(num_lst)

    count_inter = 0
    count_outer = 0
    print(num_lst)

    for i in range(l // 2):
        maxindex = i
        minindex = -i - 1
        minorigin = minindex

        for j in range(i + 1, l - i):  # 每次左右都要少比较一个
            count_inter += 1
            if num_lst[maxindex] < num_lst[j]:
                maxindex = j
            if num_lst[minindex] > num_lst[-j - 1]:
                minindex = -j - 1

        if num_lst[maxindex] == num_lst[minindex]:
            break

        if i != maxindex:
            tmp = num_lst[i]
            num_lst[i] = num_lst[maxindex]
            num_lst[maxindex] = tmp
            count_outer += 1
            # 如果最小值被交换过，则更新索引。
            # 由于i是正数，minindex必须是正数（这里是使用的负索引）。
            # 所以，第一个是极小值使用正索引的场景，第二个是极小值使用负索引的场景。
            if i == minindex or i == l + minindex:
                minindex = maxindex

        if minorigin != minindex:
            tmp = num_lst[minorigin]
            num_lst[minorigin] = num_lst[minindex]
            num_lst[minindex] = tmp
            count_outer += 1
    print(num_lst, count_inter, count_outer)


"""
改进：
"""

def test04():
    num_lst = [1, 1, 1, 1, 1, 1, 1, 1, 2]
    l = len(num_lst)

    count_inter = 0
    count_outer = 0
    print(num_lst)

    for i in range(l // 2):
        maxindex = i
        minindex = -i - 1
        minorigin = minindex

        for j in range(i + 1, l - i):  # 每次左右都要少比较一个
            count_inter += 1
            if num_lst[maxindex] < num_lst[j]:
                maxindex = j
            if num_lst[minindex] > num_lst[-j - 1]:
                minindex = -j - 1

        if num_lst[maxindex] == num_lst[minindex]:
            break

        if i != maxindex:
            tmp = num_lst[i]
            num_lst[i] = num_lst[maxindex]
            num_lst[maxindex] = tmp
            count_outer += 1
            # 如果最小值被交换过，则更新索引。
            # 由于i是正数，minindex必须是正数（这里是使用的负索引）。
            # 所以，第一个是极小值使用正索引的场景，第二个是极小值使用负索引的场景。
            if i == minindex or i == l + minindex:
                minindex = maxindex

        if minorigin != minindex:
            tmp = num_lst[minorigin]
            num_lst[minorigin] = num_lst[minindex]
            num_lst[minindex] = tmp
            count_outer += 1
    print(num_lst, count_inter, count_outer)



"""
原本只需要交换一次，现在却要交换两次，分析原因：

[1,1,1,1,1,1,1,1,2]
第一轮比较：极大值索引是8，极小值索引是-2。
极大值交换位置后：[2, 1, 1, 1, 1, 1, 1, 1, 1]
极小值交换位置后：[2, 1, 1, 1, 1, 1, 1, 1, 1]，问题在这里，由于第一轮比较极小值索引是-2，所以索引-2需要和索引-1交换。
"""
def test05():
    num_lst = [1, 1, 1, 1, 1, 1, 1, 1, 2]
    l = len(num_lst)

    count_inter = 0
    count_outer = 0
    print(num_lst)

    for i in range(l // 2):
        maxindex = i
        minindex = -i - 1
        minorigin = minindex

        for j in range(i + 1, l - i):  # 每次左右都要少比较一个
            count_inter += 1
            if num_lst[maxindex] < num_lst[j]:
                maxindex = j
            if num_lst[minindex] > num_lst[-j - 1]:
                minindex = -j - 1

        if num_lst[maxindex] == num_lst[minindex]:
            break

        if i != maxindex:
            tmp = num_lst[i]
            num_lst[i] = num_lst[maxindex]
            num_lst[maxindex] = tmp
            count_outer += 1
            # 如果最小值被交换过，则更新索引。
            # 由于i是正数，minindex必须是正数（这里是使用的负索引）。
            # 所以，第一个是极小值使用正索引的场景，第二个是极小值使用负索引的场景。
            if i == minindex or i == l + minindex:
                minindex = maxindex

        if minorigin != minindex and num_lst[minorigin] != num_lst[minindex]:
            tmp = num_lst[minorigin]
            num_lst[minorigin] = num_lst[minindex]
            num_lst[minindex] = tmp
            count_outer += 1

    print(num_lst, count_inter, count_outer)

# 测试
test05()
